321 - The New Villa (Grafos, BFS, bitwise)
[andmenj-acm.git] / 11338 - Minefield / 11338.3.cpp
blob663699de34c607f2f6b5e1300a52aa027867429d
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 #include <map>
5 #include <cmath>
6 #include <sstream>
7 #include <functional>
9 using namespace std;
11 const double infinity = 1E20;
13 struct point{
14 double x, y;
15 point(double X, double Y){ x = X; y = Y;}
18 map< point, double > dist;
20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
21 bool operator !=(const point &a, const point &b){ return !(a == b);}
22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
23 //bool operator <(point a, point b){ return (a.dist > b.dist);}
24 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
28 bool heapCmp(const point &a,const point &b){
29 return (dist[a] > dist[b]);
33 struct heapCompare : public binary_function<point, point, bool>
35 bool operator()(const point &x, const point &y) const
36 { return dist[x] > dist[y]; }
40 struct grafo{
41 //contiene todos los nodos sueltos
42 vector<point> nodos;
43 //contiene un vector con todos los vecinos para el punto point
44 map< point, vector<point> > vecinos;
46 void insert(point a){
47 if (vecinos.count(a) == 1) return; //Ya insertamos este nodo
48 nodos.push_back(a);
49 vector<point> v;
50 vecinos.insert(make_pair(a, v));
51 //printf("Insertando (%f,%f).\n", a.x, a.y);
54 void make_vecinos(double maxPath){
55 for (map< point, vector<point> >::iterator it=vecinos.begin(); it!=vecinos.end(); ++it){
56 if (distancia((*it).first, point(0.00, 0.00)) > maxPath){
57 //printf("El punto (%f,%f) es un desastre.\n", (*it).first.x, (*it).first.y);
58 continue;
60 for (map< point, vector<point> >::iterator jt = it; jt!=vecinos.end(); ++jt){
61 //Insertarlo como vecino en los nodos diferentes a el mismo
62 //printf(" Ensayando (*it).first = (%f,%f)\n", (*it).first.x, (*it).first.y);
63 if ((*it).first != (*jt).first){
64 if ((*jt).first.x - (*it).first.x > 1.5){
65 //printf("Rompiendo con a = (%f,%f) y nodos[i] = (%f,%f)\n", a.x, a.y, (*it).first.x, (*it).first.y);
66 break;
68 vector<point> adj = vecinos[(*it).first];
69 //Asegurarse de no insertar un vecino repetido
70 // if (find(adj.begin(), adj.end(), a) == adj.end()){
71 if (distancia((*jt).first, (*it).first) <= 1.5){
72 //printf("Insertando (%f,%f) como vecino de (%f,%f).\n", a.x, a.y, (*it).first.x, (*it).first.y);
73 vecinos[(*it).first].push_back((*jt).first);
74 vecinos[(*jt).first].push_back((*it).first);
76 // }
82 void initialize(){
83 dist.clear();
84 for (int i=0; i<nodos.size(); ++i){
85 dist[nodos[i]] = infinity;
86 if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
87 dist[nodos[i]] = 0.00;
92 /*void relax(point u, point v){
93 if (dist[v] > dist[u] + distancia(u, v)){
94 dist[v] = dist[u] + distancia(u, v);
96 }*/
98 void dijkstra(const double &maxPath, const point &finalPoint){
99 initialize();
101 //priority_queue<point, vector<point>, heapCompare > q(nodos.begin(), nodos.end());
102 priority_queue<point, vector<point>, heapCompare > q;
103 q.push(point(0.0, 0.0));
104 //vector<point> q(nodos.begin(), nodos.end());
105 //make_heap(q.begin(), q.end(), heapCmp);
106 while (!q.empty()){
107 //point u = q.front();
108 //pop_heap(q.begin(), q.end(), heapCmp); q.pop_back();
109 point u = q.top();
110 q.pop();
111 //printf("Saque (%f,%f) cuya distancia es %f\n", u.x, u.y, dist[u]);
112 if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
113 for (int i=0; i<vecinos[u].size(); ++i){
114 point v = vecinos[u][i];
115 //printf(" Comparando (%f,%f) con (%f,%f) que estan a %f\n", u.x, u.y, v.x, v.y, distancia(u,v));
116 //printf(" dist[u] es %f, dist[v] es %f\n", dist[u], dist[v]);
117 if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
118 //printf(" Actualizando la distancia de v = (%f,%f)\n", v.x, v.y);
119 dist[vecinos[u][i]] = dist[u] + distancia(u, v);
120 //printf(" Nueva distancia de v: %f\n", dist[v]);
121 q.push(v);
125 //make_heap(q.begin(), q.end(), heapCmp);
133 int main(){
134 while (true){
136 string s;
137 for (s = ""; s == ""; getline(cin, s));
138 if (s == "*") break;
141 grafo g;
143 stringstream line;
144 line << s;
146 int w,h;
147 line >> w >> h;
148 g.insert(point((double)w, (double)h));
149 g.insert(point(0.00, 0.00));
150 int noPuntos;
151 cin >> noPuntos;
152 for (int i=0; i<noPuntos; ++i){
153 double x,y;
154 cin >> x >> y;
155 g.insert(point(x,y));
159 double maximoCamino;
160 cin >> maximoCamino;
162 g.make_vecinos(maximoCamino);
163 //cout << "Termine de insertar todos los nodos.\n";
165 /*printf("Voy a imprimir el grafo de %d nodos:\n", g.nodos.size());
166 for (int i=0; i<g.nodos.size(); ++i){
167 printf("Estos son los vecinos de (%f,%f):\n", g.nodos[i].x, g.nodos[i].y);
168 for (int j=0; j<g.vecinos[g.nodos[i]].size(); ++j){
169 printf(" (%f,%f)\n", g.vecinos[g.nodos[i]][j].x, g.vecinos[g.nodos[i]][j].y);
173 g.dijkstra(maximoCamino, point((double)w, (double)h));
174 //printf("La distancia minima hasta (%d,%d) es %f.\n", w,h,dist[point((double)w, (double)h)]);
175 if (dist[point((double)w, (double)h)] <= maximoCamino){
176 printf("I am lucky!\n");
177 }else{
178 printf("Boom!\n");
182 return 0;